1. Field of the Invention
The present invention generally relates to the fabrication and design of semiconductor chips and integrated circuits, and more particularly to a method of designing the physical layout (placement) of logic cells in an integrated circuit, and the wiring (routing) of those cells.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements grouped to perform a logic function. Cells types include, for example, core cells, scan cells and input/output (I/O) cells. Each of the cells of an IC may have one or more pins, each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for routing, such as a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are all used for vertical and/or horizontal routing.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a xe2x80x9cnetlist,xe2x80x9d which is a record of all of the nets, or interconnections, between the cell pins. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The result is a set of design files known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design.
The present invention is directed to an improved method for designing the physical layout (placement) and wiring (routing) of cells. Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of a integrated circuit device. Due to the large number of components and the details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
A few years ago, pure standard cell designs could be considered the norm, but today""s xe2x80x9cchunkyxe2x80x9d designs contain large blocks of reserved areas for memory arrays, proprietary (IP) blocks, etc. Consequently, placement now resembles the problem of arranging xe2x80x9cdustxe2x80x9d logic around these large blocks. Since the large blocks tend to dictate the design footprint, one can no longer assume that the placeable area in some way matches the total cell area of the design; indeed, there is a marked trend of increasing percentage of free space available on the chip. One might think increased free space, or xe2x80x9cdesign sparsityxe2x80x9d, would make placement easier. However, even though the dust logic is a small percentage of the chip area, there can still be millions of cells in the dust logic that have profound effects on timing and routability.
Placement algorithms are typically based on either a simulated annealing, top-down cut-based partitioning, or analytical paradigm (or some combination thereof). Recent years have seen the emergence of several new academic placement tools, especially in the top-down partitioning and analytical domains. The advent of multilevel partitioning as a fast and extremely effective algorithm for min-cut partitioning has helped spawn a new generation of top-down cut-based placers. A placer in this class partitions the cells into either two (bisection) or four (quadrisection) regions of the chip, then recursively partitions each region until a global coarse placement is achieved. Such recursive cut-based placement can perform quite well when designs are dense, but they perform rather poorly when the designs are sparse. Sparse designs tend to fool the partitioner since it does not know how to handle the large flexibility in the balance tolerance.
Analytical placers typically solve a relaxed placement formulation (such as minimizing total quadratic wirelength) optimally, allowing cells to temporarily overlap. Legalization is achieved by removing overlaps via either partitioning or by introducing additional forces and/or constraints to generate a new optimization problem. The classic analytical placers, PROUD and GORDIAN, both iteratively use bipartitioning techniques to remove overlaps. The PROUD placer is discussed in the article by R.-S. Tsay, E. S. Kuh, and C.-P. Hsu, xe2x80x9cPROUD: A Fast Sea-of-Gates Placement Algorithmxe2x80x9d, Proc. 25th IEEE/ACM Design Automation Conference, pp. 318-323 (1988). The GORDIAN placer is discussed in the article by J. Kleinhaus, G. Sigl, F. Johannes and K. Antreich, xe2x80x9cGORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization,xe2x80x9d IEEE Trans. on Computer-Aided Design, 10(3), pp. 356-365 (1991).
Analytical placers can perform poorly when the data is naturally degenerate (which occurs when few objects are fixed to I/O ports) since it becomes difficult to legalize a placement where thousands of cells have virtually the same location. Also, analytic methods may have difficulties in dense designs where legalization is forced to significantly alter the analytic solution.
Finally, cut-based partitioners can suffer from their inability to see the global picture. FIGS. 1A-1C show a simplified example with three cells A, B and C, and one potential unit (chip) of free space. Using a conventional multilevel partitioning algorithm, the first partitioning assigns one cell A to one side, and two cells B and C to the other side. The minimum cut (min-cut) solution, i.e., minimizing the number of wires that cross, results in the placement shown in FIG. 1A. This placement is adequate, but has more total wirelength than the preferred solution shown in FIG. 1B (which has a slightly higher net cut). An analytical solver does no better, and would place all three cells to the left of the cut-line, as shown in FIG. 1C (the overlap of the cells maybe adjusted by any one of several legalization methods).
In light of the foregoing, it would be desirable to devise an improved method of designing integrated circuits which could yield placements that are more efficient (compact), having reduced total wirelengths while maintaining relatively low net cuts. A more compact distribution leads to better timing and overall performance, and additionally reduces design time, and time to market. It would be further advantageous if the method could utilize the strength of analytical placers on sparse designs to improve the poor performance of cut-based placers.
It is therefore one object of the present invention to provide an improved method of designing integrated circuits.
It is another object of the present invention to provide an improved method of placing and routing cells on an integrated circuit.
It is yet another object of the present invention to provide a method of designing the physical layout of an integrated circuit which uses an analytical engine to improve the performance of a cut-based placer.
The foregoing objects are achieved in a method of designing a layout of an integrated circuit, generally comprising the steps of deriving an analytical constraint for a cut-based placement partitioner using analytical optimization, and placing cells on an integrated circuit with the cut-based placement partitioner using the analytical constraint. In the illustrative implementation, quadratic optimization is used to determine a desired ratio of a cell area of a given partition, e.g., the left partition, to a total cell area (the balance parameter), and placing is performed using multilevel bisection partitioning constrained by the balance parameter.
More specifically, this implementation involves determining an aspect ratio for an entire partitioning region of the integrated circuit, determining a xe2x80x9ccenter-of-massxe2x80x9d coordinate of the cells based on the quadratic optimization, and defining a placement rectangle having the same aspect ratio, and centered on the center-of-mass coordinate. This placement rectangle is then used to derive the balance parameter. The placement rectangle has a total area equal to a total moveable cell area, and the balance parameter is computed by calculating the ratio of the left portion of the placement rectangle which lies in the left partition to the total area of the placement rectangle. The multilevel partitioner then places a number of cells in the left partition based on the balance parameter.
The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.